/*package demo2;

import demo1.MySingleList;

import java.util.LinkedList;
import java.util.List;

public class Solution {
    public MySingleList.ListNode partition(MySingleList.ListNode pHead, int x) {

        MySingleList.ListNode listNode1 = new MySingleList.ListNode(1);
        MySingleList.ListNode head1 = listNode1;
        MySingleList.ListNode listNode2 = new MySingleList.ListNode(1);
        MySingleList.ListNode head2 = listNode2;
        while (pHead != null) {
            if (pHead.val < x) {
                head1 = pHead;
                head1 = head1.next;
            } else {
                head2 = pHead;
                head2 = head2.next;
            }
            pHead = pHead.next;
        }
        head1.next = listNode2.next;
        return listNode1.next;
    }
    public ListNode partition1(ListNode pHead, int x) {
        ListNode listNode1 = new ListNode();
        ListNode head1 = listNode2;
        ListNode listNode2 = new ListNode();
        ListNode head2 = listNode3;
        while (pHead != null) {
            if (pHead.val < k) {
                head1 = pHead;
                head1 = head1.next;
            } else {
                head2 = pHead;
                head2 = head2.next;
            }
            pHead = pHead.next;
        }
        head1.next = listNode2.next;
        return listNode1.next;
    }
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
       ListNode listNode = new ListNode();
       ListNode head = listNode;
       while (list1!= null && list2 != null){
           if (list1.val <= list2.val){
               head.next = list1;
               list1 =  list1.next;
           }else {
               head.next = list2;
               list2 =  list2.next;

           }
           head = head.next;
       }
        if(list1 == null && list2 != null){
            head.next = list2;
        }
        if(list2 == null && list1 != null){
            head.next = list1;
        }
        return listNode;
    }
    public ListNode mergeTwoLists1(ListNode list1, ListNode list2) {
        ListNode listNode = new ListNode();

        while (list1!= null && list2 != null){
            if (list1.val <= list2.val){
                listNode.addLast(list1.val);
                list1 = list1.next;
            }else {
                listNode.addLast(list2.val);
                list2 = list2.next;
            }
        }
        if(list1 == null && list2 != null){
            listNode.addLast()
        }
        if(list2 == null && list1 != null){
            list1.next = list2;
        }
        return listNode;
    }
    public int kthToLast(ListNode h)ead, int k) {
        int num = 0;
        while(head != null){
            head = head.next;
            num++;
        }
        ListNode cur = head;
        for(int i = 0 ; i < num - k; i++){
            cur = cur.next;
        }
        return cur.val;
    }
    public ListNode middleNode(ListNode head) {
            ListNode cur = head;
            ListNode pear = head;
            while(pear != null && pear.next != null){
                cur = cur.next;
                pear = pear.next.next;
            }
            return cur;
    }
    public ListNode reverseList(ListNode head) {
        if(head == null || head.next == null){
            return head;
        }
        ListNode cur = head.next;
        ListNode pear;
        head.next = null;
        while(cur.next != null){
            pear = cur.next;
            cur.next = head;
            head = cur;
            cur = pear;
        }
        cur.next = head;
          head = cur;
          return head;
    }
    public ListNode removeElements(ListNode head, int val) {
      ListNode cur = head;
      ListNode pear;
      if(head == null){
          return head;
      }
      while(cur.next != null){
          pear = cur.next;
          if(pear.val == val){
              cur.next = pear.next;
          }else {
              cur = cur.next;
          }

      }
      if(head.val == val){
          head = head.next;
      }
      return head;
    }
}*/
